Cryptography is used to conceal communication contents. Cryptography includes a symmetric encryption scheme and an asymmetric encryption scheme. The symmetric encryption scheme uses a shared secret key in encryption processing and decryption processing. The asymmetric encryption scheme uses asymmetric keys (a public key and private key that are different from each other) in encryption processing and decryption processing.
A representative symmetric encryption scheme is AES (Advanced Encryption Standard). AES improves the security level by repeatedly processing a round function that can be processed at high speed. Note that AES has no homomorphism (to be described later).
A symmetric encryption scheme Enc is called homomorphic encryption when the following conditions are satisfied. Assume that two ciphertexts corresponding to a secret key sk and two plaintexts m1 and m2 are represented by c1=Enc(sk, m1) and c2=Enc(sk, m2). When it is possible to calculate a new ciphertext c′=c1 (*) c2=Enc(m1(+) m2) from the two ciphertexts c1 and c2 without decoding into the plaintexts m1 and m2, the encryption scheme Enc is called homomorphic encryption. Note that (*) and (+) represent operators.
When the operator (+) represents addition, the encryption scheme Enc is called additive homomorphic encryption. When the operator (+) represents multiplication, the encryption scheme Enc is called multiplicative homomorphic encryption. When there are two types of ciphertext calculation (*) for implementing additive homomorphism and multiplicative homomorphism, the encryption scheme Enc is called (somewhat) fully homomorphic encryption.
The above-described symmetric encryption scheme generally has no specific problem. From a study, however, the present inventor considers that it is possible to increase the parallelism and improve the calculation efficiency.